//Given an integer array nums, design an algorithm to randomly shuffle the array
//. 
//
// Implement the Solution class: 
//
// 
// Solution(int[] nums) Initializes the object with the integer array nums. 
// int[] reset() Resets the array to its original configuration and returns it. 
//
// int[] shuffle() Returns a random shuffling of the array. 
// 
//
// 
// Example 1: 
//
// 
//Input
//["Solution", "shuffle", "reset", "shuffle"]
//[[[1, 2, 3]], [], [], []]
//Output
//[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]
//
//Explanation
//Solution solution = new Solution([1, 2, 3]);
//solution.shuffle();    // Shuffle the array [1,2,3] and return its result. Any
// permutation of [1,2,3] must be equally likely to be returned. Example: return [
//3, 1, 2]
//solution.reset();      // Resets the array back to its original configuration 
//[1,2,3]. Return [1, 2, 3]
//solution.shuffle();    // Returns the random shuffling of array [1,2,3]. Examp
//le: return [1, 3, 2]
//
// 
//
// 
// Constraints: 
//
// 
// 1 <= nums.length <= 200 
// -106 <= nums[i] <= 106 
// All the elements of nums are unique. 
// At most 5 * 104 calls will be made to reset and shuffle. 
// 
// 👍 134 👎 0


package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

//Java：Shuffle an Array
class P384ShuffleAnArray {
    public static void main(String[] args) {
        Solution solution = new P384ShuffleAnArray().new Solution(new int[]{1, 2, 3});
        solution.shuffle();
        // TO TEST
        Random random = new Random();

        System.out.println(random.nextInt(7));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        int[] original;

        public Solution(int[] nums) {
            this.original = nums;
        }

        /**
         * Resets the array to its original configuration and return it.
         */
        public int[] reset() {
            return this.original;
        }

        /**
         * Returns a random shuffling of the array.
         */
        public int[] shuffleRemove() {
            List<Integer> list = new ArrayList<>(this.original.length);
            for (int i : this.original) {
                list.add(i);
            }
            int[] newArr = new int[this.original.length];
            Random random = new Random();
            int i = 0;
            while (list.size() > 0) {
                int range = list.size();
                int index = random.nextInt(range);
                newArr[i++] = list.get(index);
                list.remove(index);
            }
            return newArr;
        }

        public int[] shuffle() {
            int len = this.original.length;
            int[] newArr = new int[len];
            int[] result = new int[len];
            Random random = new Random();
            for (int i = 0; i < newArr.length; i++) {
                newArr[i] = -1;
            }
            for (int i = 0; i < len; i++) {
                while (true) {
                    int index = random.nextInt(len);
                    if (newArr[index] == -1) {
                        newArr[index] = i;
                        break;
                    } else {
                        continue;
                    }
                }
            }
            for (int i = 0; i < result.length; i++) {
                result[i] = this.original[newArr[i]];
            }
            return result;
        }
    }
/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int[] param_1 = obj.reset();
 * int[] param_2 = obj.shuffle();
 */
//leetcode submit region end(Prohibit modification and deletion)

}